package lanqiaobei2020;

import java.math.BigInteger;

public class _04斐波那契数列最大公约数 {
    /**
     * 斐波那契数列满足 F1 = F2 = 1F1=F2=1，从 F3F3 开始有 Fn = Fn−1 +Fn−2Fn=Fn−1+Fn−2。
     * 请你计算 GCD(F2020,F520)GCD(F2020,F520)，其中 GCD(A,B)GCD(A,B) 表示 AA 和 BB 的最大公约数
     */
    public static void main(String[] args) {
        BigInteger[] dp = new BigInteger[2021];
        dp[1] = BigInteger.ONE;
        dp[2] = BigInteger.ONE;
        for (int i = 3; i < 2021; i++) {
            dp[i] = dp[i - 1].add(dp[i - 2]);
        }
        System.out.println(gcd(dp[520], dp[2020]));

    }

    public static BigInteger gcd(BigInteger a, BigInteger b) {
        if (b.equals(BigInteger.ZERO)) {
            return a;
        }
        return gcd(b, a.mod(b));
    }
}
